package com.algomypractice.sort.timecomplexityon2;

import com.annotation.service.SortTest;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/6/13
 * @description: 插入排序(有三种 ： 直接插入 ， 折半插入 ， 希尔排序)
 */
public class InsertionSort {

	/**
	 * 直接插入排序
	 *
	 * @param arr
	 */
	@SortTest
	public static void directInsertionSort(int[] arr) {
		int len = arr.length;
		for (int i = 0; i < len; i++) {
			//插入排序
			inset(arr, i);
		}
	}

	/**
	 * 直接插入排序（在排序号的序列从后往前比）
	 *
	 * @param arr
	 */
	@SortTest
	public static void directInsertionSortDesc(int[] arr) {
		int len = arr.length;
		for (int i = 1; i < len; i++) {
			int temp;
			for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}

	/**
	 * 折半插入排序
	 * 只在寻找插入位置时进行优化-二分查找
	 * https://blog.csdn.net/weixin_42245157/article/details/80458542
	 *
	 * @param arr
	 */
	@SortTest
	public static void binaryInsertionSort(int[] arr) {
		////throw new IllegalArgumentException("未实现");
		int len = arr.length;
		///x-O(1) 空间
		int low, high, mid, i, j, x;
		for (i = 1; i < len; i++) {
			x = arr[i];
			low = 0;
			high = i - 1;
			///查找插入位置
			while (low <= high) {
				mid = (low + high) / 2;
				if (x < arr[mid]) {
					high = mid - 1;
				} else {
					low = mid + 1;
				}
			}
			///进行移位
			for (j = i; j > high + 1; j--) {
				arr[j] = arr[j - 1];
			}
			arr[j] = x;
		}
	}

	/**
	 * 希尔排序 看下时间复杂度
	 *
	 * @param arr
	 */
	@SortTest
	public static void shellSedgeWickSort(int[] arr) {
		int length = arr.length;
		int gap = 1, temp;
		while (gap < length / 3) {
			gap = (3 * gap) + 1;
		}
		while (gap >= 1) {
			for (int i = gap; i < length; ++i) {
				for (int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
					///swap(arr, j, j - gap);
					temp = arr[j];
					arr[j] = arr[j - gap];
					arr[j - gap] = temp;
				}
			}
			gap = (gap - 1) / 3;
		}
	}

	public static void shellSort(int[] arr) {
		int len = arr.length;
		int k = 1;
		List<Integer> listK = new ArrayList<>();
		while (k < len) {
			listK.add(k);
			k = k * 3 - 1;
		}
		for (int i = listK.size()-1; i >-1; i--) {
			for (int j = 0; j < listK.get(i); j++) {
				directInsertionSortDesc(arr, j, listK.get(i));
			}
		}
	}

	private static void swap(int[] arr, int index1, int index2) {
		int temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}


	private static void inset(int[] arr, int newIndex) {
		int temp = 0;
		for (int i = 0; i < newIndex - 1; i++) {
			if (arr[newIndex] < arr[i]) {
				temp = arr[newIndex];
				move(arr, i, newIndex);
				arr[i] = temp;
				break;
			}
		}
	}

	/**
	 * 将 beginIndex 开始向后移动一位
	 *
	 * @param arr
	 * @param beginIndex
	 */
	private static void move(int[] arr, int beginIndex, int newIndex) {
		for (int i = newIndex; i > beginIndex; i--) {
			arr[i] = arr[i - 1];
		}
	}

	/**
	 * 间隔的插入排序
	 *
	 * @param arr   待排序数组
	 * @param begin 开始的索引
	 * @param k     间隔
	 */
	private static void directInsertionSortDesc(int[] arr, int begin, int k) {
		int len = arr.length;
		for (int i = k + begin; i < len; i = i + k) {
			int temp;
			for (int j = i - k; j >= 0 && arr[j + k] < arr[j]; j = j - k) {
				temp = arr[j + k];
				arr[j + k] = arr[j];
				arr[j] = temp;
			}
		}
	}
}
